#include<iostream>

using namespace std;

//https://leetcode.cn/problems/reverse-linked-list/submissions/669554633
 struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };
 
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* node;
        node = _reverseList(head);
        return node;
    }

    ListNode* _reverseList(ListNode* node) {
        if (node == nullptr || node->next == nullptr) {
            return node;
        }

        ListNode* head = _reverseList(node->next);
        ListNode* cur = head;
        while (cur->next) {
            cur = cur->next;
        }
        cur->next = node;
        node->next = nullptr;

        return head;
    }
};